package com.algorithm.java.string;

/**
 *   题目:     判断两个 String 是否是互为变位词:
 *   定义:     变位词(anagrams)指的是组成两个单词的字符相同，但位置不同的单词。
 *    比如说， abbcd和abcdb就是一对变位词。
 *    也就是说，2个字符串，不管排列顺序如何，只要全部的单个字符能对应上，就是一对变位词！
 */

import com.algorithm.utils.TextUtils;

/**
 * 思路:
 *  互为变位词必须要满足:
 *   1. 两个字符串长度相同,  > 0
 *
 *   2. 字符串的 每个字符的 ASCII 值之和 相等,
 *      注: 每个 char类型字符都对应一个 ASCII 值:
 *          http://ascii.911cha.com/
 *   3. 不能直接使用 ASCII 大小求和的思路来做;
 *        例如(反例):
 *          ac --> 对应  97, 99
 *          bb --> 对应  98, 98
 *   4. 不管中文哈(不怎么能想到中文怎么转, 可能需要创建一个比较大的数组.).
 */
public class DecideString {
    //汉字会越界
    public static boolean anagram(String first, String second)throws ArrayIndexOutOfBoundsException{
        if (TextUtils.isEmpty(first) || TextUtils.isEmpty(second))
            return false;

        if (first.length() != second.length())
            return false;

        if (first.equals(second))
            return true;

        final char minChar = ' ', maxChar = '~';
        // ~ 为 ASCII 数码表 最大的取值 char,
        final int ASCII_RANGE = maxChar - minChar;

        int[] numbers = new int[ASCII_RANGE];
        int length = first.length();

        char[] fCharArray = first.toCharArray();
        char[] sCharArray = second.toCharArray();
        for (int index = 0; index < length; index++){
            //计算 字符关于  ' ' 的偏移量, 对应在 numbers 中声明的位置,
            //保证在 ' ' --> '~' 之间的所有字符都有对应的下标.
            int asciiIndex = fCharArray[index] - minChar;
            if (!checkRange(asciiIndex, minChar, maxChar))
                throw new ArrayIndexOutOfBoundsException("not support < ' ' and > '~' char");

            numbers[asciiIndex]++;

            asciiIndex = sCharArray[index] - minChar;
            if (!checkRange(asciiIndex, minChar, maxChar))
                throw new ArrayIndexOutOfBoundsException("not support < ' ' and > '~' char");

            numbers[asciiIndex]--;
        }

        //检查numbers 数组的全部字段的数据是否为0, 全为0 的时候, 即OK.
        for (int i =0 ; i < ASCII_RANGE / 2 ; i++ ) {
            int mergeSize = numbers[i];
            if ( mergeSize != 0 || 0 != numbers[ASCII_RANGE - 1 - i]){
                return false;
            }
        }

        return true;
    }

    //检测字符关于 ' ' 的偏移量范围 在 start, end 的范围内.
    private static boolean checkRange(int index, int start, int end){
        return index > start && index < end;
    }
}
